package cm.unit2.theme3;

import java.util.LinkedHashMap;
import java.util.Map;

public class FindDuplicateInArray2 {

	/**
	 * 	不修改数组找出重复的数字	
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
	public static int duplicate (int[] numbers) {
        if (numbers == null || numbers.length == 0){
            return -1;
        }
    	int start = 1;
    	int end = numbers.length-1;
    	
    	// 使用二分
    	while (end>=start) {
			int mid = ((end-start)>>1)+start;
			int count = countRange(numbers,start,mid);
			if(end==start) {
				if(count>1) {
					return start;
				}else {
					break;
				}
			}
			if(count>(mid-start+1)) {
				end = mid;
			}else {
				start = mid + 1;
			}
		}
        return -1;
    }
	
	public static int countRange(int[] numbers,int minNum,int maxNum) {
		if(numbers==null) {
			return -1;
		}
		int count = 0;
		for (int i = 0; i < numbers.length; i++) {
			if(numbers[i]>=minNum&&numbers[i]<=maxNum) {
				++count;
			}
		}
		return count;
	}
    
	public static void main(String[] args) {
		 int []array01 = {2,1,2};
		 int []array02 = {};
		 int []array03 = null;
		 int []array04 = {1,2,3,4,5};
		 
		 int r1 = FindDuplicateInArray2.duplicate(array01);
		 int r2 = FindDuplicateInArray2.duplicate(array02);
		 int r3 = FindDuplicateInArray2.duplicate(array03);
		 int r4 = FindDuplicateInArray2.duplicate(array04);
		 System.out.println(r1);
		 System.out.println(r2);
		 System.out.println(r3);
		 System.out.println(r4);
	}

}
